#include "common.h"
namespace common {
int findKth(std::vector<int> &num1, std::vector<int> &num2, const int start1,
            const int end1, const int start2, const int end2, const int k) {
    int visit_length1 = end1 - start1 + 1;
    int visit_length2 = end2 - start2 + 1;
    if (visit_length1 < visit_length2) {
        return findKth(num2, num1, start2, end2, start1, end1, k);
    }
    if (visit_length1 == 0)
        return num2[k + start2 - 1];
    if (k == 1)
        return std::min(num1[start1], num2[start2]);
    int i = start1 + std::min(visit_length1, k / 2) - 1;
    int j = start2 + std::min(visit_length2, k / 2) - 1;
    if (num1[i] > num2[j])
        return findKth(num1, num2, start1, end1, j + 1, end2,
                       k - (j - start2 + 1));
    else
        return findKth(num1, num2, i + 1, k - (i - end1 + 1), start2, end2,
                       k - (i - start1 + 1));
}
double findMedianSortedArrays(std::vector<int> &num1, std::vector<int> &num2) {
    int n = num1.size();
    int m = num2.size();
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    return (findKth(num1, num2, 0, n - 1, 0, m - 1, left) +
            findKth(num1, num2, 0, n - 1, 0, m - 1, right)) *
           0.5;
}
} // namespace common
